//给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。 
//
// 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
// 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 12
//输出：3 
//解释：12 = 4 + 4 + 4 
//
// 示例 2： 
//
// 
//输入：n = 13
//输出：2
//解释：13 = 4 + 9 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 10⁴ 
// 
//
// Related Topics 广度优先搜索 数学 动态规划 👍 1891 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class PerfectSquares {
    public static void main(String[] args) {
        Solution solution = new PerfectSquares().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 使用BFS
         * https://leetcode.cn/problems/perfect-squares/solutions/823481/shu-ju-jie-gou-he-suan-fa-bfsdong-tai-gu-jl6u/
         * @param n
         * @return
         */
        public int numSquares(int n) {
            List<Integer> list = new ArrayList<>();
            int j = 1;
            while (j*j<=n){
                list.add(j*j);
                j++;
            }

            if (list.contains(n)) return 1;
            Queue<Integer> queue = new LinkedList<>();

            queue.offer(0);
            int num = 0;
            while (!queue.isEmpty()){
                num++;
                int size = queue.size();
            }
            return 0;
        }
//        public int numSquares(int n) {
//            //arr[i] 表示 数字i最少使用平方数的个数
//            int[] arr = new int[n + 1];
//            for (int i = 1; i <= n; i++) {
//                int minSquare = Integer.MAX_VALUE;
//                //遍历i以前的平方数 也就是遍历 1～根号i获取他们的最小值
//                for (int j = 1; j * j <= i; j++) {
//                    minSquare = Math.min(minSquare, arr[i - j * j]);
//                }
//                //上面一步只是获取了最小的但是还需要加上 最小minSquare时候j的平方
//                arr[i] = minSquare + 1;
//            }
//            return arr[n];
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}